// ----------------------------------------------------------------------------
// handle_allocator.h
// ----------------------------------------------------------------------------
/*
 Description:
 リソースハンドルを管理するための基本クラス. 
 最初からリソースの最大数がわかっているデータの管理にこれを利用する. 
 空いているリソースインデックスを計算量O(1)で検索する.
 
 ※このデータハンドル作成クラスはスレッドセーフではない.
 
 ----------------------------------------------------------------
 使い方.
 
 1. データ管理を行いたいクラスに HandleAllocatorT もしくは HandleAllocator
 のインスタンスを作成する. 
 HandleAllocatorT はヒープからインスタンスを作成する場合に使い、
 HandleAllocator は任意のアロケータからインスタンスを作成する場合に使う. 
 
 class GraphicsResourceManager
 {
	...
	static const int kMaxTextureCount = 2048;
	typedef HandleAllocatorT<kMaxTextureCount> TextureIndexAllocator;
	TextureIndexAllocator m_indexAlloc;
	...
 
 2. リソースを作成する際に、HandleAllocator を使って未使用のリソースインデックスを検索する. 
 
	uint16_t textureVacancy = m_indexAlloc.Alloc();
 
 3. リソースを開放する際に開放するリソースインデックスをアロケータに伝える.
 
	m_indexAlloc.Free(textureVacancy);
 
 
 */
#pragma once
#define FW_HANDLE_ALLOCATOR_DUMP // デバッグ用途.
#include <fw/base/core/assertion.h>
#include <fw/base/core/stdinteger.h>
#include <fw/base/runtime/allocator.h>

#define FW_INVALID_HANDLE	(0xffff)

namespace fw
{
	template <uint16_t kMaxHandles> class HandleAllocatorT
	{
	private:
		uint16_t	m_handles[kMaxHandles*2];
		uint16_t	m_numHandles;
		
	public:
		static const uint16_t kInvalidHandle = FW_INVALID_HANDLE;
		
		FW_NO_INLINE HandleAllocatorT()
		: m_numHandles(0)
		{
			uint16_t* sparse = &m_handles[kMaxHandles];
			for(uint16_t handle_i=0; handle_i<kMaxHandles; ++handle_i)
			{
				m_handles[handle_i] = handle_i;
				sparse[handle_i] = kInvalidHandle;
			}
		}
		
		~HandleAllocatorT()
		{
		}
		
		const uint16_t* GetHandles() const
		{
			return m_handles;
		}
		
		uint16_t GetHandleAt(uint16_t at) const
		{
			FW_ASSERT(at<kMaxHandles);
			return m_handles[at];
		}
		
		uint16_t GetNumHandles() const
		{
			return m_numHandles;
		}
		
		uint16_t GetMaxHandles() const
		{
			return kMaxHandles;
		}
	
		uint16_t Alloc()
		{
			if(m_numHandles<kMaxHandles)
			{
				uint16_t index = m_numHandles;
				++m_numHandles;
				
				uint16_t  handle =  m_handles[index];
				uint16_t* sparse = &m_handles[kMaxHandles];
				sparse[handle]   = index;
				return handle;
			}
			return kInvalidHandle;
		}
		
		void Free(uint16_t handle)
		{
			FW_ASSERT(handle!=kInvalidHandle);
			FW_ASSERT(handle<kMaxHandles);
			
			uint16_t* sparse = &m_handles[kMaxHandles];
			uint16_t  index  =  sparse[handle];
			if(index == kInvalidHandle)
			{
				return;
			}
			--m_numHandles;
			
			uint16_t temp = m_handles[m_numHandles];
			m_handles[m_numHandles] = handle;
			sparse[temp] = index;
			m_handles[index] = temp;
			sparse[handle] = kInvalidHandle;
		}
		
		void Dump()
		{
		#if defined(FW_HANDLE_ALLOCATOR_DUMP)
			FW_PRINTF("numHandles = %d\n", m_numHandles);
			for(int handle_i=0; handle_i<kMaxHandles; ++handle_i)
			{
				FW_PRINTF("%4d:handles[%4d] sparse[%4d]\n", handle_i, m_handles[handle_i], m_handles[kMaxHandles+handle_i]);
			}
			FW_PRINTF("\n");
		#endif
		}
	}; // class HandleAllocatorT
	
	class HandleAllocator
	{
	private:
		uint16_t*	m_handles;
		uint16_t	m_numHandles;
		uint16_t	m_maxHandles;
		
	public:
		static const uint16_t kInvalidHandle = FW_INVALID_HANDLE;

		HandleAllocator(uint16_t maxHandles, void* handles)
		: m_handles(reinterpret_cast<uint16_t*>(handles))
		, m_numHandles(0)
		, m_maxHandles(maxHandles)
		{
			uint16_t* sparse = &m_handles[m_maxHandles];
			for(uint16_t handle_i=0; handle_i<maxHandles; ++handle_i)
			{
				m_handles[handle_i] = handle_i;
				sparse[handle_i] = kInvalidHandle;
			}
		}
		
		~HandleAllocator()
		{
		}
		
		const uint16_t* GetHandles() const
		{
			return m_handles;
		}
		
		uint16_t GetHandleAt(uint16_t at) const
		{
			FW_ASSERT(at<m_maxHandles);
			return m_handles[at];
		}
		
		uint16_t GetNumHandles() const
		{
			return m_numHandles;
		}
		
		uint16_t GetMaxHandles() const
		{
			return m_maxHandles;
		}
	
		uint16_t Alloc()
		{
			if(m_numHandles<m_maxHandles)
			{
				uint16_t index = m_numHandles;
				++m_numHandles;
				
				uint16_t  handle =  m_handles[index];
				uint16_t* sparse = &m_handles[m_maxHandles];
				sparse[handle]   = index;
				return handle;
			}
			return kInvalidHandle;
		}
		
		void Free(uint16_t handle)
		{
			FW_ASSERT(handle!=kInvalidHandle);
			
			uint16_t* sparse = &m_handles[m_maxHandles];
			uint16_t  index  =  sparse[handle];
			if(index == kInvalidHandle)
			{
				return;
			}
			--m_numHandles;
			
			uint16_t temp = m_handles[m_numHandles];
			m_handles[m_numHandles] = handle;
			sparse[temp] = index;
			m_handles[index] = temp;
			sparse[handle] = kInvalidHandle;
		}
		void Dump()
		{
		#if defined(FW_HANDLE_ALLOCATOR_DUMP)
			FW_PRINTF("numHandles = %d\n", m_numHandles);
			for(int handle_i=0; handle_i<m_maxHandles; ++handle_i)
			{
				FW_PRINTF("%4d:handles[%4d] sparse[%4d]\n", handle_i, m_handles[handle_i], m_handles[m_maxHandles+handle_i]);
			}
			FW_PRINTF("\n");
		#endif
		}
	}; // class HandleAllocator
	
	inline HandleAllocator* CreateHandleAllocator(Allocator& alloc, uint16_t maxHandles)
	{
		uint8_t* ptr = reinterpret_cast<uint8_t*>(alloc.Allocate(sizeof(HandleAllocator) + 2 * maxHandles * sizeof(uint16_t)));
		FW_ASSERT(ptr);
		return ::new (ptr) HandleAllocator(maxHandles, &ptr[sizeof(HandleAllocator)]);
	}
	
	inline void DestroyHandleAllocator(Allocator& alloc, HandleAllocator* handleAllocator)
	{
		FW_ASSERT(handleAllocator);
		handleAllocator->~HandleAllocator();
		alloc.Deallocate(reinterpret_cast<void*>(handleAllocator));
	}
	
} // namespace fw


